package com.czh.problem.niuku;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 牛客网刷题
 *
 * @author chenzhihua
 * @Date 2024/2/23
 */

public class SolutionNiuke {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
//        ListNode l4 = new ListNode(4);
//        ListNode l5 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;
//        l3.next = l4;
//        l4.next = l5;

        ListNode l11 = new ListNode(4);
        ListNode l12 = new ListNode(5);
        ListNode l13 = new ListNode(6);
        ListNode l14 = new ListNode(7);
//        ListNode l15 = new ListNode(15);
        l11.next = l12;
        l12.next = l13;
        l13.next = l14;
//        l14.next = l15;
//        ListNode listNode = ReverseList(l1);
//        ListNode node = reverseBetween(l1, 2, 4);
//        ListNode merge = Merge(l1, l11);
        ArrayList<ListNode> list = new ArrayList<>();
        list.add(l1);
        list.add(l11);
        ListNode merge = mergeKLists(list);
        System.out.println();
    }

    /**
     * BM1 反转链表
     */
    public static ListNode ReverseList(ListNode head) {
        //1.使用栈实现: 将链表先进栈，将第一个出栈的值作为链表头进行存储，遍历出栈然后将指针下移
//        Stack<ListNode> stack = new Stack<>();
//        // 入栈
//        while (head != null) {
//            stack.push(head);
//            head = head.next;
//        }
//        if (stack.isEmpty()) {
//            return head;
//        }
//        // 出栈
//        ListNode node = stack.pop();
//        ListNode result = node;
//        while (!stack.isEmpty()) {
//            node.next = stack.pop();
//            node = node.next;
//        }
//        node.next = null;
//        return result;


        //2.双链表求解
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode result = null;
//        while (head != null) {
//            // 先找一个临时变量来存储后面的节点
//            ListNode next = head.next;
//            // 前插法插入
//            head.next = result;
//            // 更新结果链表
//            result = head;
//            // 重新赋值
//            head = next;
//        }
//        return result;


        //3.递归实现
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = ReverseList(head.next);
        // 将当前节点的下一个节点的next指针修改成指向自己
        head.next.next = head;
        // 去除原本指向下一节点的指针
        head.next = null;
        return node;
    }

    /**
     * BM2 链表内指定区间反转
     */
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        // 因为头节点也可能被操作，所以需要在原本的头节点上添加一个虚拟的头节点
        ListNode result = new ListNode(-1);
        // 让虚拟节点指向头节点
        result.next = head;
        // 创建两个节点，一个指向虚拟头节点，一个指向真正的头节点
        ListNode pre = result;
        ListNode cur = head;

        // 将cur指向m位置，pre指向他的前一个节点
        for (int i = 1; i < m; i++) {
            pre = pre.next;
            cur = cur.next;
        }
        // 对范围内的链表进行反转
        for (int i = m; i < n; i++) {
            // 设置一个临时变量来保存当前需要翻转节点后面的数据(待翻转的数据)
            ListNode temp = cur.next;
            // 先将当前节点的下一个节点指向当前节点的下下个节点
            cur.next = cur.next.next;
            // 将待翻转节点的下一个节点指向pre的下一个节点
            temp.next = pre.next;
            // pre的next指向临时节点
            pre.next = temp;
        }
        return result.next;
    }

    /**
     * BM4 合并两个排序的链表 从小到大(双指针解法)
     */
    public static ListNode Merge(ListNode pHead1, ListNode pHead2) {
        ListNode result = new ListNode(-1);
        // 创建一个指针pre用来记录已经排序好的节点
        ListNode pre = result;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val <= pHead2.val) {
                pre.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                pre.next = pHead2;
                pHead2 = pHead2.next;
            }
            pre = pre.next;
        }
        if (pHead1 != null) {
            pre.next = pHead1;
        }
        if (pHead2 != null) {
            pre.next = pHead2;
        }
        return result.next;
    }

    /**
     * BM5 合并k个已排序的链表(优先队列) TODO 难题
     */
    public static ListNode mergeKLists(ArrayList<ListNode> lists) {
        Queue<ListNode> nodeQueue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        // 将所有节点进入队列
        for (ListNode list : lists) {
            if (list == null) continue;
            nodeQueue.offer(list);
        }
        ListNode result = new ListNode(-1);
        ListNode tail = result;
        while (!nodeQueue.isEmpty()) {
            ListNode minNode = nodeQueue.poll();
            tail.next = minNode;
            tail = minNode;
            // PriorityQueue 实现了 Queue 接口，不允许放入 null 元素
            if (minNode.next != null) {
                // 再把新的节点也加入到优先队列当中
                nodeQueue.offer(minNode.next);
            }
        }
        return result.next;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}
